home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / answrbok / 6_11.lha / 6_11 / 6_11_add.c next >
Text File  |  1993-08-08  |  4KB  |  176 lines
  1. * Copyright (c) 1990 by AT&T Bell Telephone Laboratories, Incorporated. */
  2. * The C++ Answer Book */
  3. * Tony Hansen */
  4. * All rights reserved. */
  5. *
  6.    Add u[1..n] + v[1..n] to form w[0..n]
  7.  
  8.    Based on:
  9.  
  10.    The Art of Computer Programming, volume 2
  11.    D. Knuth, Section 4.3.1, Algorithm A
  12. /
  13. include <arbint.h>
  14. include <debug.h>    /* DELETE */
  15.  
  16. rbint operator+(const arbint& u, const arbint& v)
  17.  
  18.    int ulen = u.p->length;
  19.    int vlen = v.p->length;
  20.    int wlen = max(ulen, vlen) + 1;
  21.    ARB_type *wv = new ARB_type[wlen];
  22.    ARB_type *uv = u.p->value;
  23.    ARB_type *vv = v.p->value;
  24. f (debug&64)/*DELETE*/    cerr << "operator+\n";
  25. f (debug&64)/*DELETE*/    outputarb(cerr, "u=", uv, ulen);
  26. f (debug&64)/*DELETE*/    outputarb(cerr, "v=", vv, vlen);
  27. f (debug&64)/*DELETE*/    outputarb(cerr, "w(beg)=", wv, wlen);
  28.  
  29.    /*
  30. A1 [Initialize]
  31.     set j <- n
  32.     k <- 0
  33.     { modification: uj for u, vj for v }
  34.  
  35. A3(a) [Loop on j]
  36.     decrease j by one
  37.     { modification: decrease uj and vj }
  38.    */
  39. f (debug&64)/*DELETE*/    cerr << "before first loop, uj=" << (ulen-1) << ", vj=" << (vlen-1) << ", wj=" << (wlen-1) << "\n";
  40.    ARB_Ltype k = 0;
  41.    for (int uj = ulen - 1, vj = vlen - 1, wj = wlen - 1;
  42.  uj >= 0 && vj >= 0;
  43.  uj--, vj--, wj-- )
  44. {
  45. /*
  46.     A2(a) [Add digits]
  47.     set w[j] <- (u[j] + v[j] + k) mod b
  48.     { modification: w[wj] <-
  49.       (u[uj] + v[vj] + k) mod b }
  50. */
  51. ARB_Ltype t = uv[uj] + vv[vj] + k;
  52. wv[wj] = t;    // % ARB_base;
  53.  
  54. /*
  55.     A2(b)
  56.     k <- (u[j] + v[j] + k) / b
  57. */
  58. k = (t / ARB_base) ? 1 : 0;
  59. }
  60. f (debug&64)/*DELETE*/    cerr << "after first loop, uj=" << uj << ", vj=" << vj << ", wj=" << wj << ", k=" << k << "\n";
  61. f (debug&64)/*DELETE*/    outputarb(cerr, "w(now)=", wv, wlen);
  62.  
  63.    /*
  64. NOTE: either (uj >= 0) or (vj >= 0),
  65. but not both. As long as the carry is
  66. non-zero, it must be added to the next
  67. digit.
  68.    */
  69.  
  70.    if (uj >= 0)
  71. {
  72. /*
  73.     Take care of u[1..uj].
  74. */
  75. for ( ; k != 0 && uj >= 0; uj--, wj-- )
  76.     {
  77.     ARB_Ltype t = uv[uj];
  78.     t += k;
  79.     wv[wj] = t;        // % ARB_base;
  80.     k = (t / ARB_base) ? 1 : 0;
  81.     }
  82. f (debug&64)/*DELETE*/    cerr << "after second loop, uj=" << uj << ", vj=" << vj << ", wj=" << wj << ", k=" << k << "\n";
  83. f (debug&64)/*DELETE*/    outputarb(cerr, "w(now)=", wv, wlen);
  84.  
  85. /*
  86.     The carry is now zero, so any
  87.     remaining digits can be copied.
  88. */
  89. while (uj >= 0)
  90.     wv[wj--] = uv[uj--];
  91. f (debug&64)/*DELETE*/    cerr << "after first copy, uj=" << uj << ", vj=" << vj << ", wj=" << wj << ", k=" << k << "\n";
  92. f (debug&64)/*DELETE*/    outputarb(cerr, "w(now)=", wv, wlen);
  93.  
  94. /*
  95.     If there are any digits left to be filled in
  96.     (there should be at most 1)
  97.     they must be filled with either 0
  98.     or ~0 depending on the sign of wv[wj+1]
  99. */
  100. if (wj >= 0)
  101.     {
  102.     const ARB_type hibit = (ARB_base >> 1);
  103.     const ARB_type rest = (wv[wj+1] & hibit) ? ~0 : 0;
  104.     do {
  105.     wv[wj--] = rest;
  106.     } while (wj >= 0);
  107.     }
  108. }
  109.  
  110.    else if (vj >= 0)
  111. {
  112. /*
  113.     Take care of v[1..vj]
  114. */
  115. for ( ; k != 0 && vj >= 0; vj--, wj-- )
  116.     {
  117.     ARB_Ltype t = vv[vj];
  118.     t += k;
  119.     wv[wj] = t;        // % ARB_base;
  120.     k = (t / ARB_base) ? 1 : 0;
  121.     }
  122. f (debug&64)/*DELETE*/    cerr << "after third loop, uj=" << uj << ", vj=" << vj << ", wj=" << wj << ", k=" << k << "\n";
  123. f (debug&64)/*DELETE*/    outputarb(cerr, "w(now)=", wv, wlen);
  124.  
  125. /*
  126.     The carry is now zero, so any
  127.     remaining digits can be copied.
  128. */
  129. while (vj >= 0)
  130.     wv[wj--] = vv[vj--];
  131. f (debug&64)/*DELETE*/    cerr << "after second copy, uj=" << uj << ", vj=" << vj << ", wj=" << wj << ", k=" << k << "\n";
  132. f (debug&64)/*DELETE*/    outputarb(cerr, "w(now)=", wv, wlen);
  133.  
  134. /*
  135.     If there are any digits left
  136.     (there should be at most 1)
  137.     they must be filled with either 0
  138.     or ~0 depending on the sign of wv[wj+1]
  139. */
  140. if (wj >= 0)
  141.     {
  142.     const ARB_type hibit = (ARB_base >> 1);
  143.     const ARB_type rest = (wv[wj+1] & hibit) ? ~0 : 0;
  144.     do {
  145.     wv[wj--] = rest;
  146.     } while (wj >= 0);
  147.     }
  148. }
  149.  
  150.    else
  151. {
  152. /*
  153.     If there is a digit left (there should be at
  154.     most 1), it should be set to k.
  155.     Because we are dealing with 2's complement,
  156.     a carry here means that the number must be
  157.     sign-extended; otherwise the digit is set to 0.
  158.  
  159.     A3(b)
  160.     Set w[0] <- k
  161.     { modification,
  162.       w[0] <- k ? sign(w[wj]) ? 0
  163.       }
  164. */
  165. const ARB_type hibit = (ARB_base >> 1);
  166. const ARB_type rest = (k && (wv[wj+1] & hibit)) ? ~0 : 0;
  167. while (wj >= 0)
  168.     wv[wj--] = rest;
  169. }
  170.  
  171.    /* Normalize and return */
  172. f (debug&64)/*DELETE*/        outputarb(cerr, "w(end)=", wv, wlen);
  173.    arbint w(wv, wlen);
  174.    return w;
  175.  
  176.